package com.tgy.skiplist;

import java.util.Comparator;
import java.util.Objects;

/**
 * @Author: tgy
 * @Date: 2020-11-26 13:32
 */
public class SkipList_01<K,V> {

    private final static  int MAX_LEVEL = 32;

    /**
     * 生成层数的随机值概率
     */
    private final static double P = 0.25;

    private int size;

    private Node first;

    private int level;

    private Comparator<K> comparator;

    public SkipList_01() {

        this(null);
    }

    public SkipList_01(Comparator<K> comparator) {

        this.comparator = comparator;
        first = new Node(MAX_LEVEL);
    }

    private static class Node<K,V>{

        K key;
        V val;

        Node<K,V>[] nodes;

        public Node(K key, V val, int level) {

            this.key = key;
            this.val = val;
            this.nodes = new Node[level];
        }

        public Node(int level) {

            this(null,null,level);
        }

        @Override
        public String toString() {

            return "key=" + key +";val=" + val;
        }
    }

    public boolean isEmpty() {

        return size == 0;
    }

    public V get(K key) {

        checkKey(key);

        Node<K,V> node = first;
        int cpmResul = -1;
        for (int i = level - 1; i >= 0; i--) {

            Node<K, V> nextNode  = node.nodes[i];


            while (nextNode != null && (cpmResul = cmp(key,nextNode.key)) > 0) {

                node = nextNode;
                nextNode = node.nodes[i];
            }

            // 只有等于0，说明key找到了，直接返回val
            if (cpmResul == 0) {

                return nextNode.val;
            }
        }

        return null;
    }

    public V put(K key, V val) {

        checkKey(key);


        Node<K,V>[] preNodes = new Node[level];

        Node<K,V> node = first;
        int cpmResul = -1;
        for (int i = level - 1; i >= 0; i--) {

            Node<K,V> nextNode = node.nodes[i];

            while (nextNode != null && (cpmResul = cmp(key,nextNode.key)) > 0) {

                node = nextNode;
                nextNode = node.nodes[i];
            }

            // 只有等于0，说明key找到了，直接返回val
            if (cpmResul == 0) {

                V oldVal = nextNode.val;
                nextNode.val = val;
                return oldVal;
            }

            preNodes[i] = node;
        }


        int newLevel = generateLevel();

        Node<K, V> newNode = new Node<>(key, val, newLevel);

        for (int i = newLevel - 1; i >= 0; i--) {

            if (i >= level) {

                first.nodes[i] = newNode;
            }else {

                Node<K, V> tmpNode = preNodes[i].nodes[i];
                preNodes[i].nodes[i] = newNode;
                newNode.nodes[i] = tmpNode;
            }
        }

        if (newLevel > level) {

            level = newLevel;
        }

        size++;
        return null;
    }

    public V remove(K key) {

        checkKey(key);

        Node<K,V> node = first;

        Node<K,V>[] preNodes = new Node[level];
        int cmpResult = -1;

        Node<K,V> findNode = null;

        for (int i = level - 1; i >= 0; i--) {

            Node<K,V> nextNode = node.nodes[i];

            while (nextNode != null && (cmpResult = cmp(key,nextNode.key)) > 0) {

                node = nextNode;
                nextNode = node.nodes[i];
            }

            if (cmpResult == 0) {

                findNode = nextNode;
                preNodes[i] = node;
            }

        }

        if (findNode == null) {
            return null;
        }

        for (int i = level - 1; i >= 0; i--) {

            if (preNodes[i] != null) {

                preNodes[i].nodes[i] = findNode.nodes[i];
            }
        }

        int tmp = level - 1;

        while (tmp >= 0 && first.nodes[tmp--] == null) {

            level--;
        }

        size--;

        return findNode.val;
    }


    public void printSkipList() {

        if (level == 0) {

            return;
        }

        for (int i = level - 1; i >= 0; i--) {

            Node nextNode = first.nodes[i];
            System.out.print("level:" + (i + 1) +" ");
            while (nextNode != null) {

                System.out.print("[" +nextNode + "], ");
                nextNode = nextNode.nodes[i];
            }

            System.out.println();
        }

    }

    private void checkKey(K key) {

        if (Objects.isNull(key)) {

            throw new IllegalArgumentException("key not null");
        }

    }

    private int cmp(K k1, K k2) {

        if (comparator != null) {

            return comparator.compare(k1,k2);
        }

        return ((Comparable<K>)k1).compareTo(k2);
    }

    private int generateLevel() {

        int level = 1;

        while (Math.random() < P) {

            level++;
        }
        return level > MAX_LEVEL ? MAX_LEVEL:level;
    }
}
